import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val=val;
    }
}
public class BfsAndCengXu {
    //二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            //在每一层遍历开始前，先记录队列中的结点数量n（也就是这一层的结点数量），然后一口气处理完这一层的n个结点。将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。
            List<Integer> levelNodes = new ArrayList<>();//每一层一个List数组

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelNodes.add(node.val);

                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            result.add(levelNodes);//[[,]]
        }

        return result;
    }

    // 二叉树的广度遍历
    public List<Integer> BfsBinary(TreeNode root){
        List<Integer> resultList = new ArrayList<>();
        if (root == null) return resultList;

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(root);//offer()比add()稍好，可以对异常处理有所调控,但一般刷题都行

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            resultList.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        // 创建一棵二叉树示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 实例化BFSTraversal对象
        BfsAndCengXu traversal = new BfsAndCengXu();
        // 调用levelOrder方法进行广度优先遍历(但是是层序遍历)，区分每一层，返回二维数组
        List<List<Integer>> result = traversal.levelOrder(root);
        // 输出结果
        System.out.println("层序遍历输出："+result);

        //广度优先搜索，BFS 的遍历结果是一个一维数组，无法区分每一层
        BfsAndCengXu t=new BfsAndCengXu();
        List<Integer> result1=t.BfsBinary(root);
        System.out.println("Bfs遍历输出："+result1);
    }
}